package mess;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeeCode_51_failed {
    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(5);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.println(s);
            }
            System.out.println();
        }
    }

    private static List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        if (n == 1){
            List<String> list = new ArrayList<>();
            list.add("Q");
            res.add(list);
            return res;
        }
        if (n == 2 || n == 3)
            return res;

        //初始化
        char[][] chars = new char[n][n];
        chars[0][0] = '.';
        chars[0][n - 1] = '.';
        for (int i = 1; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                if (chars[i - 1][j] != '.'){
                    chars[i][j] = '.';
                }
            }
        }

        //向下搜寻
        for (int first = 1; first < n - 1; first++) {
            char[][] newChars = new char[n][n];
            for (int i = 0; i < n; i++) {
                newChars[i] = Arrays.copyOfRange(chars[i], 0, n);
            }
            //第一行搜寻加初始化
            newChars[0][first] = 'Q';
            for (int temp = 0; temp < n - 1; temp++) {
                if (temp == first)
                    continue;
                newChars[0][temp] = '.';
            }
            //第二行开始搜寻加初始化
            for (int i = 1; i < n / 2; i++) {
                for (int j = 0; j < n; j++) {
                    if (newChars[i][j] != '.'){
                        if (j == 0 && newChars[i - 1][j + 1] != 'Q'){
                            //左边界符合条件
                            newChars[i][j] = 'Q';
                            for (int temp = 1; temp < n; temp++) {
                                newChars[i][temp] = '.';
                            }
                        }
                        else if (j > 0 && j < n - 1){
                            if (newChars[i - 1][j - 1] != 'Q' && newChars[i - 1][j + 1] != 'Q'){
                                //中间符合条件
                                newChars[i][j] = 'Q';
                                for (int temp = 0; temp < n; temp++) {
                                    if (temp == j)
                                        continue;
                                    newChars[i][temp] = '.';
                                }
                            }
                        }
                        else if (j == n - 1 && newChars[i - 1][j - 1] != 'Q'){
                            //右边界符合条件
                            newChars[i][j] = 'Q';
                            for (int temp = 0; temp < n - 1; temp++) {
                                newChars[i][temp] = '.';
                            }
                        }
                    }
                }
            }
            //搜寻完毕, 构造结果
            List<String> newRes = new ArrayList<>();
            for (int i = 0; i < n / 2; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    sb.append(newChars[i][j]);
                }
                newRes.add(sb.toString());
            }
            for (int i = n / 2 - 1; i >= 0; i--) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    sb.append(newChars[i][j]);
                }
                newRes.add(sb.reverse().toString());
            }
            res.add(newRes);
        }

        return res;
    }
}
